Nowadays, video sequential alignment has shown great value in many video applications such as scene detection, content monitoring, and so on. The alignment of two sequences can be seen as a path finding problem through a cost matrix. That is, the alignment of the two sequences can be converted to find a path from the lower left corner to the upper right corner. Each dimension represents the frame features of one sequence.
Traditional approaches use dynamic time warping (DTW) algorithms (e.g., Needleman-Wunsch global sequence alignment algorithm, Dijkstra's algorithm, etc.) to align such two time sequences. That is, the DTW algorithms are used to find the possible alignment of two sequences which may differ in some parts. For example, a Needleman-Wunsch global sequence alignment algorithm performs global alignment on two sequences and finds the alignment with the maximum score. But these algorithms consume excessive time and memory resources when the sequences become large, as the complexity of the problem is given as O(NM), where N and M are the dimension of the matrix. Therefore, these approaches have a quadratic time and space complexity that limits its use to small time series.
The disclosed method and apparatus are directed to solve one or more problems set forth above and other problems.